package com.wfm.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map.Entry;
import java.util.TreeMap;
import org.junit.Test;

public class PLCP57打地鼠{
//leetcode submit region begin(Prohibit modification and deletion)
public class Solution {
    public int getMaximumNumber(int[][] moles) {
        int n = moles.length;
        int[][] dp = new int[n + 1][9]; // 9 表示 3*3 格子的所有位置
        int[] dx = {0, 0, 1, -1}; // 锤子移动的方向
        int[] dy = {1, -1, 0, 0};

        // 初始化第 0 秒时锤子在 (1,1) 位置
        dp[0][1 * 3 + 1] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 9; j++) {
                int row = j / 3;
                int col = j % 3;
                dp[i][j] = dp[i - 1][j]; // 不移动锤子的情况
                for (int k = 0; k < 4; k++) {
                    int prevRow = row + dx[k];
                    int prevCol = col + dy[k];
                    if (prevRow >= 0 && prevRow < 3 && prevCol >= 0 && prevCol < 3) {
                        int prevPos = prevRow * 3 + prevCol;
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][prevPos]); // 从其他位置移动过来的情况
                    }
                }
                // 检查当前位置是否有地鼠
                for (int[] mole : moles) {
                    if (mole[0] == i - 1 && mole[1] - 1 == row && mole[2] - 1 == col) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j] + 1);
                    }
                }
            }
        }

        // 找出所有位置中的最大值
        int maxMoles = 0;
        for (int i = 0; i < 9; i++) {
            maxMoles = Math.max(maxMoles, dp[n][i]);
        }
        return maxMoles;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PLCP57打地鼠().new Solution();
//        int[][] ints = {{2,0,2}, {6,2,0}, {4,1,0},{2,2,2},{3,0,2}};
        int[][] ints = {{1, 1, 0}, {2, 0, 1}, {4, 2, 2}};
        int maximumNumber = solution.getMaximumNumber(ints);
        System.out.println(maximumNumber);
    }


    @Test
    public void test(){
        int[][] ints = {{2,0,2}, {6,2,0}, {4,1,0},{2,2,2},{3,0,2}};
        TreeMap<Integer,List<int[]>> map = new TreeMap<>();
        for (int[] mole : ints) {
            if(!map.containsKey(mole[0])){
                List<int[]> value = new ArrayList<>();
                value.add(mole);
                map.put(mole[0],value);
            }else {
                map.get(mole[0]).add(mole);
            }
        }
        while (!map.isEmpty()){
            Entry<Integer, List<int[]>> integerListEntry = map.pollFirstEntry();
            System.out.println(integerListEntry.getKey());
            System.out.println(Arrays.deepToString(integerListEntry.getValue().toArray()));
        }

    }
}